package com.duoduo.demo.math;

import java.util.Arrays;
import java.util.Random;

public class SudoTest {

	public static void main(String[] args) {
		// 列出4*4所有数独
		// sudoSelect(new String[] {
		// "1", "2", "3", "4"
		// });

		// 列出9*9所有数独
		// sudoSelect(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// });

		// 列出16*16所有数独
		// sudoSelect(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G"
		// });

		// 列出9*9所有对角线数独
		// sudoSelect(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// }, true);

		// 求解给定数独所有可能
		// sudoSelect(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// }, new String[][] {
		// {
		// "8", "", "", "", "", "", "", "", ""
		// }, {
		// "", "", "3", "6", "", "", "", "", ""
		// }, {
		// "", "7", "", "", "9", "", "2", "", ""
		// }, {
		// "", "5", "", "", "", "7", "", "", ""
		// }, {
		// "", "", "", "", "4", "5", "6", "", ""
		// }, {
		// "", "", "", "1", "", "", "", "3", ""
		// }, {
		// "", "", "1", "", "", "", "", "6", "8"
		// }, {
		// "", "", "8", "5", "", "", "", "1", ""
		// }, {
		// "", "9", "", "", "", "", "4", "", ""
		// }
		// });

		// 求解所有可能（对角线数独）
		// sudoSelect(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// }, new String[][] {
		// {
		// "", "2", "", "", "", "", "", "", ""
		// }, {
		// "5", "", "6", "", "", "", "3", "", "9"
		// }, {
		// "", "8", "", "5", "", "2", "", "6", ""
		// }, {
		// "", "", "5", "", "7", "", "1", "", ""
		// }, {
		// "", "", "", "2", "", "8", "", "", ""
		// }, {
		// "", "", "4", "", "1", "", "8", "", ""
		// }, {
		// "", "5", "", "8", "", "7", "", "3", ""
		// }, {
		// "7", "", "2", "", "", "", "4", "", "5"
		// }, {
		// "", "4", "", "", "", "", "", "7", ""
		// }
		// }, true);

		// 生成数独（生成的可能无解或有多个解）
		// sudoGenerator(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// }, 30);

		// 生成对角线数独（生成的可能无解或有多个解）
		// sudoGenerator(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// }, 25, true);

		// 求解给定数独所有可能
		// sudoSelect(new String[] {
		// "1", "2", "3", "4", "5", "6", "7", "8", "9"
		// }, new String[][] {
		// {
		// "9", "1", "2", "0", "0", "7", "0", "5", "0"
		// }, {
		// "0", "0", "3", "0", "5", "9", "0", "2", "1"
		// }, {
		// "0", "0", "5", "4", "1", "2", "0", "0", "9"
		// }, {
		// "0", "8", "0", "0", "4", "5", "9", "0", "2"
		// }, {
		// "0", "0", "0", "0", "7", "0", "5", "0", "0"
		// }, {
		// "5", "0", "4", "0", "6", "0", "0", "1", "0"
		// }, {
		// "0", "0", "0", "5", "0", "6", "0", "0", "0"
		// }, {
		// "2", "5", "0", "7", "0", "0", "8", "0", "0"
		// }, {
		// "0", "3", "0", "0", "0", "0", "0", "9", "5"
		// }
		// });

		// 求解给定数独所有可能
		// http://tieba.baidu.com/p/4813549830
		// #9806 002300609000000075100060000504100008060050040800007102000030001250000000907004200
		// #9807 010000000000294000008300709180002040050000080030800096401003800000471000000000020
		// #9808 100200905000080000400600023010005060000060000050400030840001007000070000507002001
		// #9809 300500090400000500002310000053080010000090000060050370000021800001000004080007006
		// #9810 010500000090073000804020000400000100780060029002000005000030207000480060000006090
		// sudoSelect("002300609000000075100060000504100008060050040800007102000030001250000000907004200");
		// sudoSelect("010000000000294000008300709180002040050000080030800096401003800000471000000000020");
		// sudoSelect("100200905000080000400600023010005060000060000050400030840001007000070000507002001");
		// sudoSelect("300500090400000500002310000053080010000090000060050370000021800001000004080007006");
		// sudoSelect("010500000090073000804020000400000100780060029002000005000030207000480060000006090");
		sudoSelect("030205040008000005600000000040001307020090080801700060000000009100000600080104050");
	}

	/**
	 * 9*9数独给定已选字符串求解
	 * @param resultString 数独题目
	 */
	public static void sudoSelect(String resultString) {
		String[][] resultArray = initResultArray(resultString);
		sudoSelect(new String[] {
				"1", "2", "3", "4", "5", "6", "7", "8", "9"
		}, resultArray);
	}

	/**
	 * N*N数独求解所有可能组合
	 * @param dataArray 待选列表
	 */
	public static void sudoSelect(String[] dataArray) {
		String[][] resultArray = initResultArray(dataArray);
		sudoSelect(dataArray, resultArray);
	}

	/**
	 * N*N数独给定结果数组求解
	 * @param dataArray 待选列表
	 * @param resultArray 已选结果数组
	 */
	public static void sudoSelect(String[] dataArray, final String[][] resultArray) {
		sudoSelect(dataArray, resultArray, false);
	}

	/**
	 * N*N数独求解所有可能组合（对角线）
	 * @param dataArray 待选列表
	 * @param checkCross 是否校验对角线
	 */
	public static void sudoSelect(String[] dataArray, boolean checkCross) {
		String[][] resultArray = initResultArray(dataArray);
		sudoSelect(dataArray, resultArray, checkCross);
	}

	/**
	 * N*N数独求解所有可能组合（对角线）
	 * @param dataArray 待选列表
	 * @param resultArray 已选结果
	 * @param checkCross 是否校验对角线
	 */
	public static void sudoSelect(String[] dataArray, final String[][] resultArray, boolean checkCross) {
		sudoSelect(dataArray, resultArray, 0, checkCross);
	}

	/**
	 * N*N数独求解
	 * @param dataArray 待选列表
	 * @param resultArray 前面（resultIndex-1）个的选择结果
	 * @param resultIndex 选择索引，从0开始至（N*N-1）
	 * @param checkCross 是否对角线
	 */
	private static void sudoSelect(String[] dataArray, final String[][] resultArray, int resultIndex,
			boolean checkCross) {
		int resultLen = resultArray.length;
		if (resultIndex >= (int) Math.pow(resultLen, 2)) {
			// 全部选择完时，输出排列结果
			printResult(resultArray);
			return;
		}

		int row = (int) resultIndex / resultLen;
		int col = resultIndex % resultLen;
		if (isUnselect(resultArray[row][col])) {
			// 逐个尝试，递归选择下一个
			for (int i = 0; i < dataArray.length; i++) {
				if (checkAll(resultArray, row, col, dataArray[i], checkCross)) {
					// 排列结果不存在该项，才可选择
					String[][] resultCopy = copyArray(resultArray);

					resultCopy[row][col] = dataArray[i];
					sudoSelect(dataArray, resultCopy, resultIndex + 1, checkCross);
				}
			}
		} else {
			// 递归选择下一个
			String[][] resultCopy = copyArray(resultArray);
			sudoSelect(dataArray, resultCopy, resultIndex + 1, checkCross);
		}
	}

	/**
	 * 校验是否已经选择好
	 * @param value
	 * @return
	 */
	private static boolean isUnselect(String value) {
		return "".equals(value) || "0".equals(value);
	}

	/**
	 * 执行所有校验
	 * @param resultArray
	 * @param row
	 * @param col
	 * @param value
	 * @param checkCross
	 * @return
	 */
	private static boolean checkAll(final String[][] resultArray, int row, int col, String value, boolean checkCross) {
		// 行校验
		if (!checkRow(resultArray, row, value)) {
			return false;
		}

		// 列校验
		if (!checkColumn(resultArray, col, value)) {
			return false;
		}

		// 宫校验
		if (!checkBlock(resultArray, row, col, value)) {
			return false;
		}

		// 对角线校验
		if (checkCross) {
			// 对角线校验（左上至右下）
			if (!checkLeftTop2RightBottom(resultArray, row, col, value)) {
				return false;
			}
			// 对角线校验（左下至右上）
			if (!checkLeftBottom2RightTop(resultArray, row, col, value)) {
				return false;
			}
		}

		return true;
	}

	/**
	 * 行校验
	 * @param resultArray
	 * @param row
	 * @param value
	 * @return
	 */
	private static boolean checkRow(final String[][] resultArray, int row, String value) {
		int arrayLen = resultArray.length;
		for (int i = 0; i < arrayLen; i++) {
			if (value.equals(resultArray[row][i])) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 列校验
	 * @param resultArray
	 * @param col
	 * @param value
	 * @return
	 */
	private static boolean checkColumn(final String[][] resultArray, int col, String value) {
		int arrayLen = resultArray.length;
		for (int i = 0; i < arrayLen; i++) {
			if (value.equals(resultArray[i][col])) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 宫校验
	 * @param resultArray
	 * @param row
	 * @param col
	 * @param value
	 * @return
	 */
	private static boolean checkBlock(final String[][] resultArray, int row, int col, String value) {
		int arrayLen = resultArray.length;
		int blockLen = (int) Math.sqrt(arrayLen);
		int blockRowIndex = (int) row / blockLen;
		int blockColIndex = (int) col / blockLen;
		int blockRowStart = blockLen * blockRowIndex;
		int blockColStart = blockLen * blockColIndex;

		for (int i = 0; i < blockLen; i++) {
			int rowIndex = blockRowStart + i;
			for (int j = 0; j < blockLen; j++) {
				int colIndex = blockColStart + j;
				if (value.equals(resultArray[rowIndex][colIndex])) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 对角线校验（左上至右下）
	 * @param resultArray
	 * @param value
	 * @return
	 */
	private static boolean checkLeftTop2RightBottom(final String[][] resultArray, int row, int col, String value) {
		if (row == col) {
			int arrayLen = resultArray.length;
			for (int i = 0; i < arrayLen; i++) {
				if (value.equals(resultArray[i][i])) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 对角线校验（左下至右上）
	 * @param resultArray
	 * @param value
	 * @return
	 */
	private static boolean checkLeftBottom2RightTop(final String[][] resultArray, int row, int col, String value) {
		int arrayLen = resultArray.length;
		if ((row + col) == (arrayLen - 1)) {
			for (int i = 0; i < arrayLen; i++) {
				if (value.equals(resultArray[arrayLen - i - 1][i])) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 数独生成器
	 * @param dataArray 待选列表
	 * @param genCount 生成的个数
	 */
	public static void sudoGenerator(String[] dataArray, int genCount) {
		sudoGenerator(dataArray, genCount, false);
	}

	/**
	 * 数独生成器
	 * @param dataArray 待选列表
	 * @param genCount 生成的个数
	 * @param checkCross 是否是对角线数独
	 */
	public static void sudoGenerator(String[] dataArray, int genCount, boolean checkCross) {
		int arrayLen = dataArray.length;
		String[][] resultArray = initResultArray(dataArray);

		int count = 0;
		while (count < genCount) {
			int row = (new Random()).nextInt(arrayLen);
			int col = (new Random()).nextInt(arrayLen);
			if (isUnselect(resultArray[row][col])) {
				// 尝试随机生成10次
				for (int i = 0; i < 10; i++) {
					int value = (new Random()).nextInt(arrayLen - 1) + 1;
					if (checkAll(resultArray, row, col, "" + value, checkCross)) {
						resultArray[row][col] = "" + value;
						count++;
						break;
					}
				}
				// 若随机不行尝试循环处理
				if (isUnselect(resultArray[row][col])) {
					for (int i = 1; i <= arrayLen; i++) {
						if (checkAll(resultArray, row, col, "" + i, checkCross)) {
							resultArray[row][col] = "" + i;
							count++;
							break;
						}
					}
				}
			}
		}

		System.out.println("生成题目：\n--------------------------------\n");
		printResult(resultArray);
		System.out.println("\n参考答案：\n--------------------------------");
		sudoSelect(dataArray, resultArray);
	}

	/**
	 * 初始化结果数组
	 * @param resultString 结果字符串
	 * @return
	 */
	public static String[][] initResultArray(String resultString) {
		int arrayLen = 9;
		String[][] resultArray = new String[arrayLen][arrayLen];
		for (int i = 0; i < arrayLen; i++) {
			for (int j = 0; j < arrayLen; j++) {
				resultArray[i][j] = "" + resultString.charAt(i * arrayLen + j);
			}
		}
		return resultArray;
	}

	/**
	 * 初始化结果数组
	 * @param dataArray 待选列表
	 * @return
	 */
	public static String[][] initResultArray(String[] dataArray) {
		int arrayLen = dataArray.length;
		String[][] resultArray = new String[arrayLen][arrayLen];
		for (int i = 0; i < arrayLen; i++) {
			for (int j = 0; j < arrayLen; j++) {
				resultArray[i][j] = "0";
			}
		}
		return resultArray;
	}

	/**
	 * 复制数组
	 * @param array
	 * @return
	 */
	private static String[][] copyArray(final String[][] array) {
		int rowCount = array.length;
		int colCount = array[0].length;
		String[][] copy = new String[rowCount][colCount];
		for (int i = 0; i < rowCount; i++) {
			for (int j = 0; j < colCount; j++) {
				copy[i][j] = array[i][j];
			}
		}
		return copy;
	}

	private static int resultIndex = 0;

	/**
	 * 输出结果（限制100个）
	 * @param resultArray
	 */
	private static void printResult(final String[][] resultArray) {
		System.out.println(++resultIndex + "\n--------------------------------");
		int arrayLen = resultArray.length;
		for (int i = 0; i < arrayLen; i++) {
			System.out.println(Arrays.asList(resultArray[i]));
		}
		if (resultIndex >= 100) {
			System.exit(0);
		}
	}
}
